{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Largest Continuous Sum\n",
    "\n",
    "## Problem\n",
    "Given an array of integers (positive and negative) find the largest continuous sum. \n",
    "\n",
    "## Solution\n",
    "\n",
    "If the array is all positive, then the result is simply the sum of all numbers. The negative numbers in the array will cause us to need to begin checking sequences.  \n",
    "\n",
    "The algorithm is, we start summing up the numbers and store in a current sum variable. After adding each element, we check whether the current sum is larger than maximum sum encountered so far. If it is, we update the maximum sum. As long as the current sum is positive, we keep adding the numbers. When the current sum becomes negative, we start with a new current sum. Because a negative current sum will only decrease the sum of a future sequence. Note that we don’t reset the current sum to 0 because the array can contain all negative integers. Then the result would be the largest negative number. \n",
    "\n",
    "Let's see the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def large_cont_sum(arr): \n",
    "    \n",
    "    # Check to see if array is length 0\n",
    "    if len(arr)==0: \n",
    "        return 0\n",
    "    \n",
    "    # Start the max and current sum at the first element\n",
    "    max_sum=current_sum=arr[0] \n",
    "    \n",
    "    # For every element in array\n",
    "    for num in arr[1:]: \n",
    "        \n",
    "        # Set current sum as the higher of the two\n",
    "        current_sum=max(current_sum+num, num)\n",
    "        \n",
    "        # Set max as the higher between the currentSum and the current max\n",
    "        max_sum=max(current_sum, max_sum) \n",
    "        \n",
    "    return max_sum "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "large_cont_sum([1,2,-1,3,4,10,10,-10,-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "Many times in an interview setting the question also requires you to report back the start and end points of the sum. Keep this in mind and see if you can solve that problem, we'll see it in the mock interview section of the course!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "from nose.tools import assert_equal\n",
    "\n",
    "class LargeContTest(object):\n",
    "    def test(self,sol):\n",
    "        assert_equal(sol([1,2,-1,3,4,-1]),9)\n",
    "        assert_equal(sol([1,2,-1,3,4,10,10,-10,-1]),29)\n",
    "        assert_equal(sol([-1,1]),1)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "#Run Test\n",
    "t = LargeContTest()\n",
    "t.test(large_cont_sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
